import java.util.Arrays;
import java.util.Random;

public class Main {
     public static void main(String[] args) {
        // *** （了解）计数排序****
        //1.
        //思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
        //1. 统计相同元素出现次数
        //2. 根据统计的结果将序列回收到原来的序列中

        // 使用场景：给出指定范围内的数据进行排序

        //【计数排序的特性总结】
        //1. **计数排序在数据范围集中时**，效率很高，但是适用范围及场景有限。
        //2. 时间复杂度：O(MAX(N,范围))
        // 3. 空间复杂度：O(范围)
        // 4. 稳定性：稳定
        int[] array = {1,5,2,1,1,3,4};
        Sort.countSort(array);
        System.out.println(Arrays.toString(array));

    }
    public static void main10(String[] args) {
        // ****排序算法复杂度及稳定性分析****

    }
       public static void main9(String[] args) {
        // ****归并排序****
        // 也是用到二叉树的思想

        //2.4.1 基本思想
        //归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
        // Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使
        //子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
        // 先分解再合并
        // 当有序表分解为只有1个元素的时候分解结束
        // 再用递归继续操作两边,先递归完左边再递归右边

        // 对于序列 10 6 7 1 3 9 4 2


        // 2.4.2 归并排序总结
        //1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
        //2. 时间复杂度：O(N*logN)
        // 3. 空间复杂度：O(N)
        // 4. 稳定性：稳定
        int[] array = {12,56,32,67,10,19,4};
        // Sort.quickSort(array);
      //  Sort.mergeSort(array);
        Sort.mergeSort2(array);
        System.out.println(Arrays.toString(array));


        //2.4.3 海量数据的排序问题
        //外部排序：排序过程需要在磁盘等外部存储进行的排序
        //前提：内存只有 1G，需要排序的数据有 100G
        //因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
        //1. 先把文件切分成 200 份，每个 512 M
        // 2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
        //3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了


    }
     public static void main8(String[] args) {
        // 2.3.2 快速排序
        //快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元
        //素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有
        //元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止


        // 一般情况下选两边作为基准值

        int[] array = {12,56,32,67,10,19,4};
        Sort.quickSort(array);
        System.out.println(Arrays.toString(array));

        // 那么有一个问题
        // 本代码中是以左边的最为基准
        // 那么为什么左边做key(基准)的时候要先走右边呢
        // 如果先从左边走的话 ，左右相遇后，会出现比基准大的值被换到基准前面的位置

        // 快排是有可能存在栈溢出的异常



    }
       public static void main7(String[] args) {
        //2.3 交换排序
        //基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特
        //点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
        int[] array = {12,56,32,67,10,19,4};
        Sort.bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void main6(String[] args) {
        // **** 选择排序 ****

        //2.2.1基本思想：
        //每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元
        //素排完
        int[] array = {12,56,32,67,10,19,4};
      //  Sort.selectSort(array);
      //  Sort.selectSort2(array);
        Sort.heapSort(array);
        System.out.println(Arrays.toString(array));

    }

    public static void main3(String[] args) {
        // **** 希尔排序 ****

        //希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，
        //所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达
        //  =1时，所有记录在统一组内排好序

        int[] array = {12,56,32,67,10,19,4};
        Sort.shellSort(array);
        System.out.println(Arrays.toString(array));
    }
    //这个main 与 main1 进行速度上的比较
    // 给一个有序的数据
    private  static void iniArrayOrder(int[] array){
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
           // array[i] = array.length-i;  //这一行是逆序的
        }
    }

    //给一个无序的数据
    private  static void iniArrayNotOrder(int[] array){
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt();
        }
    }
    public static void testInsertSort(int[] array){
        array =  Arrays.copyOf(array,array.length);  // 必须要拷贝一份
        // 目的是 为了预防在另一个排序中会影响到这个数组

        // 在插入之前记录一个时间
        long startTime = System.currentTimeMillis();  // 返回当前时间的一个毫秒
        Sort.insertSort(array);
        long endTime = System.currentTimeMillis();  // 返回当前时间的一个毫秒
        System.out.println("直接插入排序耗时:"+(endTime - startTime));

    }

    public static void testShellSort(int[] array){
       array = Arrays.copyOf(array,array.length);
    }

    public static void main(String[] args) {
        int[] array = new int[10_0000];
        // 给一个有序数组
        iniArrayOrder(array);  // 有序的数组
       // iniArrayNotOrder(array); // 无序的数组
        // 接下来进行测试
        testInsertSort(array);

        testShellSort(array); // copyOf之后这一行是不受影响的
    }
    public static void main1(String[] args) {

        // **** 排序的概念及应用****

        //1.1 排序的概念
        //排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

        //稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持
        //不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳
        //定的；否则称为不稳定的。

        //内部排序：数据元素全部放在内存中的排序。

        //外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

        // 插入排序
        int[] array = {12,56,32,67,10,19,4};
        Sort.insertSort(array);
        System.out.println(Arrays.toString(array));

    }
}